#include<iostream>
#include<queue>

using namespace std;

int minimumMeetingRoom(vector<vector<int>> intervals){
    if(intervals.size() == 0) return 0;

    sort(intervals.begin(), intervals.end());

    //最小堆，存储会议最早结束时间
    priority_queue<int, vector<int>, greater<int>> ending ; 
    ending.push(intervals[0][1]);

    int rowCount = intervals.size();
    for(int i = 1; i < rowCount; i++){
        int leastEnding = ending.top();
        cout<<"leastEnding: "<<leastEnding<<" intervals[i][0] "<<intervals[i][0]<<endl;
        if(intervals[i][0] >= leastEnding){
            //会议开始时间 比最早结束的会议晚，有空闲会议室，复用现有会议室
            ending.pop();
            cout<<"复用，更新最小堆"<<i<<endl;
        }

        ending.push(intervals[i][1]);
        cout<<ending.size()<<endl;
        
    }

    

    return ending.size();

}

void print(vector<vector<int>> input){
    for (auto row : input){
        for(auto col : row){
            cout<<col<<" ";
        }
        cout<<endl;
    }
}

int main(){

    vector<vector<int>> input = {{20, 30}, {15, 21}, {15, 20}};
    // vector<vector<int>> input = {{7,10}, {2,4}};
    // vector<vector<int>> input = {{0 , 30}, {5, 10}, {15, 20}};
    cout<<"before sort"<<endl;
    print(input);
    sort(input.begin(), input.end());
    cout<<"after sort"<<endl;
    print(input);

    int ret = minimumMeetingRoom(input);
    cout<<"ret is: "<<ret<<endl;
    return 0;
}


